\section{Introduction}

DiGr (pronounced to rhyme with ``tiger'') is a compiled, imperative,
object oriented language designed to easily create, process and modify
directed graphs. Directed graphs are simple yet flexible graph theory
concepts which show up in everything from basic computer science data
structures to gaming. Fundamental objects and operations in DiGr make
it easy to quickly and efficiently define trees and graphs, and then
modify, search, traverse and otherwise interact with them. DiGr also
provides support for more abstract concepts like tree traversals and
value hierarchies.

DiGr is a language in which nodes and edges are the most natural
objects. Its syntax allows for the creation of nodes, edges, and
entire graph structures with small, concise statements. In DiGr, the
user can write the minimum amount of information needed to define the
digraph, and the compiler will intelligently fill in the rest of the
details. Each node and directed edge efficiently stores any additional
amount of user information, allowing for a wide variety of user
applications. Where possible, DiGr tries to hide implementation
details from the user: for example, undirected graphs are compiled as
a special type of directed graph, and tree traversal queues present
only a minimal front-end to the user. 

In DiGr, it is also easy to crawl and manipulate digraphs. ``Crawls''
are a special type of function defined in a way convenient for
depth-first, breadth-first, or any other type of user-defined
traversals of digraphs. That is, the most primitive function in the
language is a recursive one that moves from parent to children
nodes. Crawls are general enough to be useful in many graph-related
applications, but narrowly defined enough to let the user do a lot
while writing a little.

When given a start node and a ``rule'' by the user, crawls use an
internal queue to move through and examine or modify a directed
graph. The user defines which action, if any, the crawl takes at a
given node. The rule guides graph traversal by determining the
structure of the queue at each step. For example, three variants
depth-first search variants are implemented by changing the order in
which the rule adds children to the queue. In a conditional path
traversal, the crawl maintains a queue with a single node in it.

\subsection{What Problems Can DiGr Solve?}

DiGr can be applied to a number of problems which can be modeled and
solved using basic graph theory operations and ideas. These span from
the academic and abstract to more down to earth applications, from
finding the best route between points based on various criteria
(distance, cost, time required), to designing and modeling search
trees and search algorithms for fast storage and look-up of data
(contacts lists, dictionary definitions, computer process trees), to
even fancier applications like implement finite state machines (and,
by extension, regular expressions). Here is a specific example.

A main concern in commercial shipping is getting the products to their
destination in as economical a fashion as possible, be it the economy
of time, money, or some other factor. Thus it is very important to
have an easy yet sophisticated model of the shipping lanes, factories,
and destinations involved. The DiGr language is ideal for describing
and manipulating the kind of data that a route planner would deal
with.

The factories and destinations are represented as DiGr nodes and the
shipping lanes that connect them are DiGr edges. The attributes of the
edges could represent weight or importance based on a number of
factors including distance, frequency traveled, difficulty of
transportation, etc. When shipping lanes are temporarily disabled,
say, due to weather, those edges could be represented as ``broken'';
the connection would still exist, but an attribute would render it
inactive. Different choice of rules in specially written crawls could
select routes by speed or efficiency (e.g. ``take the edge with less
financial cost'', ``take the edge of shorter distance'') and return
two very different routes.  Adding and modifying the network are very
natural low-level operations in the DiGr language, as are ways to
modify and examine the network.

